/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=GACS25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]

␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1978

␈↓ ↓H␈↓␈↓ ¬yMIDTERM
␈↓ ↓H␈↓␈↓ εOctober 26

␈↓ ↓H␈↓α␈↓ ¬iProgramming


␈↓ ↓H␈↓        Write␈α∂LISP␈α⊂programs␈α∂for␈α∂each␈α⊂of␈α∂the␈α⊂functions␈α∂described␈α∂below.␈α⊂ The␈α∂function␈α⊂scan␈α∂be
␈↓ ↓H␈↓written␈α⊂in␈α∂either␈α⊂internal␈α∂or␈α⊂external␈α∂notation.␈α⊂ Assume␈α∂a␈α⊂reasonable␈α∂number␈α⊂of␈α⊂functions␈α∂are
␈↓ ↓H␈↓system␈α∂defined␈α∂(e.g.␈α∂APPEND,␈α∂REVERSE,␈α∂PLUS,␈α⊂etc.)␈α∂but␈α∂when␈α∂in␈α∂doubt,␈α∂write␈α⊂the␈α∂function
␈↓ ↓H␈↓yourself.

␈↓ ↓H␈↓1.1)␈α␈↓↓depth[x]␈↓␈αis␈αthe␈αlength␈αof␈αthe␈αlongest␈αpath␈α(from␈αroot␈αto␈αleaf)␈αin␈α␈↓↓x.␈α␈↓␈αHere␈α␈↓↓x␈↓␈αis␈αan␈αS-expression
␈↓ ↓H␈↓␈↓ α(which␈αrepresents␈αa␈αbinary␈αtree.␈α The␈αfollowing␈αis␈αone␈αi/o␈αpair␈αwhich␈αsatisfies␈αthe␈αfunction
␈↓ ↓H␈↓␈↓ α(definition.

␈↓ ↓H␈↓␈↓ β↓␈↓↓depth[␈↓¬((A . (B . C)) . (E . F))␈↓↓] = 3   (note B and C are deepest)␈↓ 

␈↓ ↓H␈↓1.2)␈α
␈↓↓hb[x,n]␈↓␈α
is␈α
true␈αiff␈α
the␈α
binary␈α
tree␈αrepresented␈α
by␈α
the␈α
S-expression␈α
␈↓↓x␈↓␈αhas␈α
the␈α
property␈α
that␈αit␈α
is
␈↓ ↓H␈↓␈↓ α(height␈αbalanced␈αfor␈αparameter␈α␈↓↓n.␈↓␈α A␈αbinary␈αtree␈αis␈αheight␈αbalanced␈αif␈αeach␈αnode␈αis␈αheight
␈↓ ↓H␈↓␈↓ α(balanced␈α∞with␈α∞respect␈α∞to␈α∞␈↓↓n.␈↓␈α∂ A␈α∞node␈α∞is␈α∞height␈α∞balanced␈α∂with␈α∞respect␈α∞to␈α∞␈↓↓n␈↓␈α∞if␈α∂the␈α∞longest
␈↓ ↓H␈↓␈↓ α(branch␈αon␈αthe␈αleft␈αis␈αwithin␈α␈↓↓n␈↓␈αof␈α
the␈αlongest␈αbranch␈αon␈αthe␈αright.␈α The␈αfollowing␈α
are␈αtwo
␈↓ ↓H␈↓␈↓ α(i/o pairs which satisfy the funtion definition.

␈↓ ↓H␈↓␈↓ βλ␈↓↓hb[␈↓¬((A . B) . (C . D)) 0␈↓↓] = TRUE (the tree is perfectly balanced)␈↓ 

␈↓ ↓H␈↓␈↓ ∧≠␈↓↓hb[␈↓¬(((A . B) . (C . D)). D) 1␈↓↓] = FALSE␈↓ 

␈↓ ↓H␈↓2)␈α
␈↓↓permutation[u,v]␈↓␈α
is␈α
true␈α∞iff␈α
␈↓↓v␈↓␈α
is␈α
a␈α
permuation␈α∞of␈α
␈↓↓u.␈↓␈α
 This␈α
means␈α
that␈α∞the␈α
list␈α
␈↓↓v␈↓␈α
is␈α
just␈α∞a␈α
re-
␈↓ ↓H␈↓␈↓ α(arrangement␈α
of␈α
the␈α
list␈α
␈↓↓u.␈↓␈α
 Note:␈α
 it␈α
is␈α
possible␈α
for␈α
an␈α
element␈α
of␈α
␈↓↓u␈↓␈α
to␈α
appear␈α
a␈αmultiple
␈↓ ↓H␈↓␈↓ α(number␈αof␈αtimes␈αin␈α␈↓↓u.␈↓␈α This␈αis␈αfine␈αas␈αlong␈αas␈αit␈αappears␈αthe␈αsame␈αnumber␈αof␈αtimes␈αin␈α␈↓↓v.␈α␈↓
␈↓ ↓H␈↓␈↓ α(The following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ β;␈↓↓permutation[␈↓¬(A B C C B F G) (G C B B A F C)␈↓↓] = TRUE␈↓ 

␈↓ ↓H␈↓3)␈α
␈↓↓polymult[p1,p2]␈↓␈α
multiplies␈α
two␈α
polynomials␈α
in␈α
one␈α
variable␈α
together.␈α
 The␈α
representation␈αof␈α
the
␈↓ ↓H␈↓␈↓ α(polynomial␈α
5x↑3␈α∞-␈α
3x↑2␈α
+␈α∞2␈α
is␈α∞the␈α
list␈α
of␈α∞coefficients␈α
(5␈α∞-3␈α
0␈α
2).␈α∞ The␈α
result␈α∞of␈α
␈↓↓polymult␈↓
␈↓ ↓H␈↓␈↓ α(should␈α∞again␈α∞be␈α∞a␈α∞list␈α
of␈α∞coefficients␈α∞with␈α∞no␈α∞leading␈α
0's.␈α∞ The␈α∞following␈α∞is␈α∞one␈α∞i/o␈α
pair
␈↓ ↓H␈↓␈↓ α(which satisfies the function definition.

␈↓ ↓H␈↓␈↓ ∧H␈↓↓polymult[␈↓¬(3 1 4) (4 1)␈↓↓] = (12 7 17 4)␈↓ 
␈↓ ↓H␈↓α␈↓ ε∩Proving␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓        Given␈α∂the␈α⊂following␈α∂function␈α∂descriptions␈α⊂prove␈α∂the␈α∂required␈α⊂theorems.␈α∂ Be␈α⊂explicit␈α∂and
␈↓ ↓H␈↓rigorous␈αin␈αrecording␈αyour␈αproof.␈α Justify␈αeach␈αindividual␈αstep␈α(i.e.␈αfunction␈αexpansion,␈αinduction
␈↓ ↓H␈↓hypothesis,␈α∩etc.).␈α∩ The␈α∩only␈α∩theorems␈α∩you␈α∩may␈α∩assume␈α∩have␈α∩been␈α∩previously␈α∩proved␈α∩are␈α∩the
␈↓ ↓H␈↓associativity␈α
of␈α
append␈α
and␈α
that␈α∞NIL␈α
is␈α
the␈α
identity␈α
for␈α
append␈α∞(on␈α
either␈α
side).␈α
 If␈α
you␈α∞need␈α
a
␈↓ ↓H␈↓lemma, prove it.

␈↓ ↓H␈↓↓      reverse[u] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ reverse[␈↓αd|␈↓↓u] * [␈↓αa|␈↓↓u . ␈↓¬NIL␈↓↓]

␈↓ ↓H␈↓↓      fringe[x] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ [x . ␈↓¬NIL␈↓↓]
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ fringe[␈↓αa|␈↓↓x] * fringe[␈↓αd|␈↓↓x]

␈↓ ↓H␈↓↓      mirror[x] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ x
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ mirror[␈↓αd|␈↓↓x] . mirror[␈↓αa|␈↓↓x]

␈↓ ↓H␈↓1) mirror[mirror[x]] = x

␈↓ ↓H␈↓2) fringe[mirror[x]] = reverse[fringe[x]]
␈↓ ↓H␈↓␈↓ ∧+COMPUTER SCIENCE DEPARTMENT␈↓ ↓H␈↓␈↓ εH␈↓ 92
␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1978


␈↓ ↓H␈↓α␈↓ ¬KMidterm Solutions


␈↓ ↓H␈↓α␈↓ ¬iProgramming

␈↓ ↓H␈↓↓1.1)
␈↓ ↓H␈↓↓      depth[x] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ 0
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ 1+max[depth[␈↓αa|␈↓↓x],depth[␈↓αd|␈↓↓x]]

␈↓ ↓H␈↓↓1.2)
␈↓ ↓H␈↓↓      hb[x,n] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ TRUE
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ hb[␈↓αa|␈↓↓x] ∧ hb[␈↓αd|␈↓↓x] ∧ abs[depth[␈↓αa|␈↓↓x]-depth[␈↓αd|␈↓↓x]]≤n

␈↓ ↓H␈↓↓2)
␈↓ ↓H␈↓↓      permutation[u,v] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓αn|␈↓↓v
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ member[␈↓αa|␈↓↓u,v] ∧ permutation[␈↓αd|␈↓↓u,remove[␈↓αa|␈↓↓u,v]]

␈↓ ↓H␈↓↓      remove[x,v] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ x = ␈↓αa|␈↓↓v ␈↓αthen␈↓↓ ␈↓αd|␈↓↓v
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ ␈↓αa|␈↓↓v . remove[x,␈↓αd|␈↓↓v]

␈↓ ↓H␈↓↓3)
␈↓ ↓H␈↓↓      polymult[p1,p2] ← 
␈↓ ↓H␈↓↓              polymult1[p1,reverse[p2],length[p1]+length[p2]-1,1]

␈↓ ↓H␈↓↓      polymult1[p1,rp2,n1,n2] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ n1=0 ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓
␈↓ ↓H␈↓↓               conv[trunc[p1,n1],trunc[rp2,n2]] . polymult1[p1,rp2,n1-1,n2+1]

␈↓ ↓H␈↓↓      conv[u,v] ←
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ∨ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ 0
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ [␈↓αa|␈↓↓u] x [␈↓αa|␈↓↓v] + conv[␈↓αd|␈↓↓u,␈↓αd|␈↓↓v]

␈↓ ↓H␈↓↓      trunc[u,n] ← 
␈↓ ↓H␈↓↓              ␈↓αif␈↓↓ length[u]≤n ␈↓αthen␈↓↓ u
␈↓ ↓H␈↓↓              ␈↓αelse␈↓↓ trunc[␈↓αd|␈↓↓u,n]
␈↓ ↓H␈↓α␈↓ ε∩Proving␈↓ ↓H␈↓␈↓ εH␈↓ 93

␈↓ ↓H␈↓¬1) mirror[mirror[x]] = x

␈↓ ↓H␈↓¬   a) Base Case: x is an atom

␈↓ ↓H␈↓¬        mirror[mirror[x]] = mirror[x]                           Def. mirror
␈↓ ↓H␈↓¬                          = x                                   Def. mirror

␈↓ ↓H␈↓¬   b) Inductive Step: x is an S-expression but not an atom

␈↓ ↓H␈↓¬        mirror[mirror[x]]
␈↓ ↓H␈↓¬                = mirror[mirror[dx] . mirror[ax]]               Def. mirror
␈↓ ↓H␈↓¬                = mirror[mirror[ax]] . [mirror [mirror[dx]]     Def. mirror
␈↓ ↓H␈↓¬                = ax . dx                                       Induction hyp.
␈↓ ↓H␈↓¬                = x                                             Def. of a,d,.


␈↓ ↓H␈↓¬2) fringe[mirror[x]] = reverse[fringe[x]]

␈↓ ↓H␈↓¬   a) Base Case: x is an atom

␈↓ ↓H␈↓¬        fringe[mirror[x]] = fringe[x]                           Def. mirror
␈↓ ↓H␈↓¬                          = x . NIL                             Def. fringe
␈↓ ↓H␈↓¬                          = reverse[x . NIL]                    Def. reverse
␈↓ ↓H␈↓¬                          = reverse[fringe[x]]                  Def. fringe
␈↓ ↓H␈↓¬ 
␈↓ ↓H␈↓¬   b) Inductive Step: x is an S-expression but not an atom

␈↓ ↓H␈↓¬        fringe[mirror[x]]
␈↓ ↓H␈↓¬                = fringe[mirror[dx] . mirror[ax]]               Def. mirror
␈↓ ↓H␈↓¬                = fringe[mirror[dx]] * fringe[mirror[ax]]       Def. fringe
␈↓ ↓H␈↓¬                = reverse[fringe[dx]] * reverse[fringe[ax]]     Induction hyp.
␈↓ ↓H␈↓¬                = reverse[fringe[ax] * fringe[dx]]              lemma 1
␈↓ ↓H␈↓¬                = reverse[fringe[x]]                            Def. fringe

␈↓ ↓H␈↓¬Lemma for 2)
␈↓ ↓H␈↓¬  reverse[u*v]=reverse[v] * reverse[u]

␈↓ ↓H␈↓¬   a) Base Case: x is NIL

␈↓ ↓H␈↓¬        reverse[u*v] = reverse[v]                               Def. append
␈↓ ↓H␈↓¬                     = reverse[v] * NIL                         Ident. of *
␈↓ ↓H␈↓¬                     = reverse[v] * reverse[u]                  Def. append

␈↓ ↓H␈↓¬   b) Inductive Step: x is a non-null list

␈↓ ↓H␈↓¬        reverse[u*v] = reverse[au . du * v]                     Def. append
␈↓ ↓H␈↓¬                     = reverse[du * v] * [au . NIL]             Def. reverse
␈↓ ↓H␈↓¬                     = [reverse[v] * reverse[du]] * [au . NIL]  Induction hyp.
␈↓ ↓H␈↓¬                     = reverse[v] * [reverse[du] * [au . NIL]]  Assoc. of *
␈↓ ↓H␈↓¬                     = reverse[v] * reverse[u]                  Def. reverse